package morris;

public class Morris {
    public static void main(String[] args) {
        Node head = new Node(1);
       head.left = new Node(2);
       head.right = new Node(3);
       head.left.left = new Node(4);
       head.left.right = new Node(5);
       head.right.left = new Node(6);
       head.right.right = new Node(7);

//        morrisPre(head);
        morrisInOrder(head);
    }

    static class Node{
        int val;
        Node left;
        Node right;
        public Node(int val) {
            this.val = val;
        }
    }
    public static void morris(Node head){
        if(head == null){
            return;
        }
        Node curr = head;
        Node rightMost = null;
        while(curr != null){
            rightMost = curr.left;
            if(rightMost != null){
                while(rightMost.right != null && rightMost.right != curr){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = curr;
                    curr = curr.left;
                    continue;
                }else{
                    rightMost.right = null;
                }
            }
            curr = curr.right;
        }
    }
    public static void morrisPre(Node head){
        if(head == null){
            return;
        }
        Node curr = head;
        Node rightMost = null;
        while(curr != null){
            rightMost = curr.left;
            if(rightMost != null){
                while(rightMost.right != null && rightMost.right != curr){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = curr;
                    System.out.println(curr.val);
                    curr = curr.left;
                    continue;
                }else{
                    rightMost.right = null;
                }
            }else{
                System.out.println(curr.val);
            }
            curr = curr.right;
        }
    }

    public static void morrisInOrder(Node head){
   /*     if(head == null){
            return;
        }
        Node curr = head;
        Node rightMost = null;
        while(curr != null){
            rightMost = curr.left;
            if(rightMost != null){
                while(rightMost.right != null && rightMost.right != curr){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = curr;
                    curr = curr.left;
                    continue;
                }else{
                    rightMost.right = null;
                    System.out.println(curr.val);
                }
            }else{
                System.out.println(curr.val);
            }
            curr = curr.right;
        }*/
        if(head == null){
            return;
        }
        Node curr = head;
        Node rightMost = null;
        while(curr != null){
            rightMost = curr.left;
            if(rightMost != null){
                while(rightMost.right != null && rightMost.right != curr){
                    rightMost = rightMost.right;
                }
                if(rightMost.right == null){
                    rightMost.right = curr;
                    curr = curr.left;
                    continue;
                }else{
                    rightMost.right = null;
                }
            }
            System.out.println(curr.val);
            curr = curr.right;
        }
    }
}
